1. Field of the Invention
The present invention relates to a packet switching system and in particular to a pipelined scheduling method and system implemented in the packet switching system.
2. Description of the Prior Art
With the growing demand for bandwidth, there is an increasing need for high-speed switching. To meet such a demand, there has been widely used a crossbar switch having N input ports and N output ports, where each input port has N logical queues each corresponding to the N output ports.
As a promising scheduling protocol applicable to the above reservation at the predetermined future time slot can be completed during N time slots prior to the predetermined future time slot. Such scheduling is performed at each time slot by pipeline processing to achieve N×N scheduling for future time slots.
More specifically, as shown in FIG. 1B, assuming N=5, the scheduling module S1 starts scheduling for the future time slot T6 at the time slot T1 and the following scheduling modules S2 to S5 sequentially perform scheduling for the future time slot T6 at respective time slots T2-T5. Shifting the phase of this scheduling process for the time slot T6 by one time slot, the scheduling module S5 starts scheduling for the future time slot T7 at the time slot T2 and the following scheduling modules S1, to S4 sequentially perform scheduling for the future time slot T7 at respective time slots T3-T6. In this manner, a scheduling module starting each scheduling process sequentially changes in the order presented: S1, S3, S4, S3, and S2. Therefore, all the scheduling modules S1-S2, equally have the right to start a scheduling process.
In this way, N×N scheduling for future time slots is performed by pipeline processing, resulting in high-speed packet forwarding.
In the case where a plurality of adjacent inputs request the same output in the same scheduling process, however, the conventional scheduling method has disadvantages that all the inputs do not have an equal chance of reservation. The unfairness in reservation chance is caused by the fixed connection among the scheduling modules.
Assuming that both Input 2 and Input 3 continue to concurrently request the same Output 4 without any other request, the reservation chance proportion between the Input 2 and the Input 3 is 4:1. Such unfairness is caused by the fact that the number of times the scheduling module S3, makes a reservation earlier than the scheduling module S3 is 4 times higher than the number of times the scheduling module S, makes a reservation earlier than the scheduling module S2. More specifically, as shown in FIG. 1B, at the time slots T6, T7, T8, and T10, the scheduling module S2 makes a reservation earlier than the scheduling module S3. Only at the time slot T9, the scheduling module S3 makes a reservation earlier than the scheduling module S2. Therefore, the reservation chance proportion between the Input 2 and the Input 3 becomes 4:1.
When any two adjacent inputs simultaneously request the same output, the reservation chance proportion between them becomes 4:1. When any three adjacent inputs simultaneously request the same output, the reservation chance proportion between them becomes 3:1:1. In general, when any L adjacent inputs simultaneously request the same output, the reservation chance proportion between them becomes (N−L+1):1:1 . . . . Therefore, the larger the number of Input/output lines. N, the greater the unfairness. In the case of N=20, the reservation chance proportion between two adjacent inputs is 19:1.
Furthermore, output port reservation at a predetermined future time slot needs N time slots prior to the predetermined future time slot. Therefore, the fixed delay time for packet forwarding is N time slots and the fixed delay time increases as the number of input/output line, N, increases. In the case of N=20, the fixed delay time is 20 time slots.